This paper investigates search techniques for multi-agent settings in which the most suitable agent, according to given criteria, needs to be found. In particular, it considers the case where the searching agent incurs a cost for learning the value of an agent and the goal is to minimize the expected overall cost of search by iteratively increasing the extent of search. This kind of search is applicable to various domains, including auctions, first responders, and sensor networks. Using an innovative transformation of the extents-based sequence to a probability-based one, the optimal sequence is proved to consist of either a single search iteration or an infinite sequence of increasing search extents. This leads to a simplified characterization of the the optimal search sequence from which it can be derived. This method is also highly useful for legacy economic-search applications, where all agents are considered suitable candidates and the goal is to optimize the search process as a whole. The effectiveness of the method for both best-valued search and economic search is demonstrated numerically using a synthetic environment.

Planning with temporally extended goals and uncontrollable events has recently been introduced as a formal model for system reconfiguration problems. An important application is to automatically reconfigure a real-life system in such a way that its subsequent internal evolution is consistent with a temporal goal formula. In this paper we introduce an incremental search algorithm and a search-guidance heuristic, two generic planning enhancements. An initial problem is decomposed into a series of subproblems, providing two main ways of speeding up a search. Firstly, a subproblem focuses on a part of the initial goal. Secondly, a notion of action relevance allows to explore with higher priority actions that are heuristically considered to be more relevant to the subproblem at hand. Even though our techniques are more generally applicable, we restrict our attention to planning with temporally extended goals and uncontrollable events. Our ideas are implemented on top of a successful previous system that performs online learning to better guide planning and to safely avoid potentially expensive searches. In experiments, the system speed performance is further improved by a convincing margin.

In this paper we show how taking advantage of autonomous agents' capability to maintain parallel interactions with others, and incorporating it into the cooperative economic search model results in a new search strategy which outperforms current strategies in use. As a framework for our analysis we use the electronic marketplace, where buyer agents have the incentive to search cooperatively. The new search technique is quite intuitive, however its analysis and the process of extracting the optimal search strategy are associated with several significant complexities. These difficulties are derived mainly from the unbounded search space and simultaneous dual affects of decisions taken along the search. We provide a comprehensive analysis of the model, highlighting, demonstrating and proving important characteristics of the optimal search strategy. Consequently, we manage to come up with an efficient modular algorithm for extracting the optimal cooperative search strategy for any given environment. A computational based comparative illustration of the system performance using the new search technique versus the traditional methods is given, emphasizing the main differences in the optimal strategy's structure and the advantage of using the proposed model.